package leetcode; /**
 * description:
 * author:zt
 * date:2021-08-16
 */

/**
 * 路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
 *
 * 路径和 是路径中各节点值的总和。
 *
 * 给你一个二叉树的根节点 root ，返回其 最大路径和 。
 */
public class leetcode124 {
    int ans = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        dfs(root);
        return ans;
    }
    public int dfs(TreeNode root){
        //叶子节点以下的节点只能返回0
        if (root==null) return 0;

        //left表示root的左叶子节点能给root的最大贡献，right同理
        //所求的值即为 一个节点+左子节点最大贡献+右子节点最大贡献
        int left = dfs(root.left);
        int right = dfs(root.right);
        ans = Math.max(ans,root.val+left+right);
        int max = Math.max(left,right)+root.val;
        return max<0? 0:max;
    }
}
